{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Move Pieces to Obtain a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canChange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移动片段得到字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串 <code>start</code> 和 <code>target</code> ，长度均为 <code>n</code> 。每个字符串 <strong>仅</strong> 由字符 <code>'L'</code>、<code>'R'</code> 和 <code>'_'</code> 组成，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符 <code>'L'</code> 和 <code>'R'</code> 表示片段，其中片段 <code>'L'</code> 只有在其左侧直接存在一个 <strong>空位</strong> 时才能向 <strong>左</strong> 移动，而片段 <code>'R'</code> 只有在其右侧直接存在一个 <strong>空位</strong> 时才能向 <strong>右</strong> 移动。</li>\n",
    "\t<li>字符 <code>'_'</code> 表示可以被 <strong>任意</strong> <code>'L'</code> 或 <code>'R'</code> 片段占据的空位。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果在移动字符串 <code>start</code> 中的片段任意次之后可以得到字符串 <code>target</code> ，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>start = \"_L__R__R_\", target = \"L______RR\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>可以从字符串 start 获得 target ，需要进行下面的移动：\n",
    "- 将第一个片段向左移动一步，字符串现在变为 \"<strong>L</strong>___R__R_\" 。\n",
    "- 将最后一个片段向右移动一步，字符串现在变为 \"L___R___<strong>R</strong>\" 。\n",
    "- 将第二个片段向右移动三步，字符串现在变为 \"L______<strong>R</strong>R\" 。\n",
    "可以从字符串 start 得到 target ，所以返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>start = \"R_L_\", target = \"__LR\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>字符串 start 中的 'R' 片段可以向右移动一步得到 \"_<strong>R</strong>L_\" 。\n",
    "但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>start = \"_R\", target = \"R_\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == start.length == target.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>start</code> 和 <code>target</code> 由字符 <code>'L'</code>、<code>'R'</code> 和 <code>'_'</code> 组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [move-pieces-to-obtain-a-string](https://leetcode.cn/problems/move-pieces-to-obtain-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [move-pieces-to-obtain-a-string](https://leetcode.cn/problems/move-pieces-to-obtain-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"_L__R__R_\"\\n\"L______RR\"', '\"R_L_\"\\n\"__LR\"', '\"_R\"\\n\"R_\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if start.replace('_', '') != target.replace('_', ''):\n",
    "            return False\n",
    "        j = 0\n",
    "        for i, c in enumerate(start):\n",
    "            if c == '_': continue\n",
    "            while target[j] == '_': \n",
    "                j += 1\n",
    "            if i != j and (c == 'L') == (i < j):\n",
    "                return False\n",
    "            j += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        # 性质1 字母需要一一对应\n",
    "        if start.replace('_', '') != target.replace('_', ''):\n",
    "            return False\n",
    "        \n",
    "        # 保证完性质1，下面就可以一一对应\n",
    "        # 性质2 start[i] target[j]\n",
    "        # L: i >= j R: i <= j\n",
    "        j = 0\n",
    "        for i, ch in enumerate(start):\n",
    "            if ch == '_': continue\n",
    "            while j < len(target) and target[j] == '_': j += 1\n",
    "            if ch == 'L': \n",
    "                if i < j: return False\n",
    "            else:\n",
    "                if i > j: return False\n",
    "            j += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s1 = \"\"\n",
    "        t1 = \"\"\n",
    "        l = len(start)\n",
    "        for i in range(l):\n",
    "            if start[i] != \"_\":\n",
    "                s1 = s1 + start[i]\n",
    "            if target[i] != \"_\":\n",
    "                t1 = t1 + target[i]\n",
    "        if s1 != t1:\n",
    "            return False\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < l and j < l:\n",
    "            while i < l and start[i] == \"_\":\n",
    "                i = i + 1\n",
    "            while j < l and target[j] == \"_\":\n",
    "                j = j + 1\n",
    "            if i < l and j < l:\n",
    "                if start[i] == \"L\" and i < j:\n",
    "                    return False\n",
    "                if start[i] == \"R\" and i > j:\n",
    "                    return False\n",
    "                i = i + 1\n",
    "                j = j + 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        cnt = 0\n",
    "        n = len(start)\n",
    "        start = list(start)\n",
    "        for i in range(n):\n",
    "            if start[i] == \"R\":\n",
    "                if cnt > 0 or target[i] == \"L\": return False\n",
    "            elif start[i] == \"L\":\n",
    "                if target[i] == \"_\":\n",
    "                    if cnt==0:  return False\n",
    "                    cnt -= 1\n",
    "                    start[i] = \"_\"\n",
    "            else:\n",
    "                if target[i] == \"L\":\n",
    "                    cnt += 1\n",
    "                    start[i] = \"L\" \n",
    "        \n",
    "        if cnt > 0: return False\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if start[i] == \"L\":\n",
    "                if cnt > 0 or target[i] == \"R\": return False\n",
    "            elif start[i] == \"R\":\n",
    "                if target[i] == \"_\":\n",
    "                    if cnt==0:  return False\n",
    "                    cnt -= 1\n",
    "            else:\n",
    "                if target[i] == \"R\":\n",
    "                    cnt += 1\n",
    "        return cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        cnt = 0\n",
    "        n = len(start)\n",
    "        start = list(start)\n",
    "        for i in range(n):\n",
    "            if start[i] == \"R\":\n",
    "                if cnt > 0 or target[i] == \"L\": return False\n",
    "            elif start[i] == \"L\":\n",
    "                if target[i] == \"_\":\n",
    "                    if cnt==0:  return False\n",
    "                    cnt -= 1\n",
    "                    start[i] = \"_\"\n",
    "            else:\n",
    "                if target[i] == \"L\":\n",
    "                    cnt += 1\n",
    "                    start[i] = \"L\" \n",
    "        \n",
    "        if cnt > 0: return False\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if start[i] == \"L\":\n",
    "                if cnt > 0 or target[i] == \"R\": return False\n",
    "            elif start[i] == \"R\":\n",
    "                if target[i] == \"_\":\n",
    "                    if cnt==0:  return False\n",
    "                    cnt -= 1\n",
    "            else:\n",
    "                if target[i] == \"R\":\n",
    "                    cnt += 1\n",
    "        return cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if \"\".join(start.split(\"_\")) != \"\".join(target.split(\"_\")):\n",
    "            return False\n",
    "\n",
    "        j = -1\n",
    "        for i in range(len(start)):\n",
    "            if start[i] == \"_\":\n",
    "                continue\n",
    "            else:\n",
    "                while j < len(target):\n",
    "                    j += 1\n",
    "                    if target[j] == \"_\":\n",
    "                        continue\n",
    "                    else:\n",
    "                        break\n",
    "                if start[i] == \"R\" and i > j:\n",
    "                    return False\n",
    "                elif start[i] == \"L\" and i < j:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        length = len(start)\n",
    "        j=0\n",
    "        if ''.join(start.split('_'))!=''.join(target.split('_')):\n",
    "            return False\n",
    "        for i in range(length):\n",
    "            if target[i]=='L':\n",
    "                while j<length and start[j]!='L':\n",
    "                    if start[j]=='R':\n",
    "                        return False\n",
    "                    j+=1\n",
    "                if start[j]!='L' or j<i:\n",
    "                    return False\n",
    "                j+=1\n",
    "            if target[i]=='R':\n",
    "                while j<length and start[j]!='R':\n",
    "                    if start[j]=='L':\n",
    "                        return False\n",
    "                    j+=1\n",
    "                if start[j]!='R' or j>i:\n",
    "                    return False\n",
    "                j+=1\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        length = len(start)\n",
    "        j=0\n",
    "        if ''.join(start.split('_'))!=''.join(target.split('_')):\n",
    "            return False\n",
    "        for i in range(length):\n",
    "            if target[i]=='L':\n",
    "                while j<length and start[j]!='L':\n",
    "                    if start[j]=='R':\n",
    "                        return False\n",
    "                    j+=1\n",
    "                if start[j]!='L' or j<i:\n",
    "                    return False\n",
    "                j+=1\n",
    "            if target[i]=='R':\n",
    "                while j<length and start[j]!='R':\n",
    "                    if start[j]=='L':\n",
    "                        return False\n",
    "                    j+=1\n",
    "                if start[j]!='R' or j>i:\n",
    "                    return False\n",
    "                j+=1\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        start_L, start_R, target_L, target_R = 0, 0, 0, 0\n",
    "        start_lst = []\n",
    "        target_lst = []\n",
    "        for i in range(n):\n",
    "            start_L += 1 if start[i] == \"L\" else 0\n",
    "            start_R += 1 if start[i] == \"R\" else 0\n",
    "            target_L += 1 if target[i] == \"L\" else 0\n",
    "            target_R += 1 if target[i] == \"R\" else 0\n",
    "            if start[i] != \"_\":\n",
    "                start_lst.append(start[i])\n",
    "            if target[i] != \"_\":\n",
    "                target_lst.append(target[i])\n",
    "            if start_L > target_L or start_R < target_R:\n",
    "                return False\n",
    "        if start_lst != target_lst:\n",
    "            return False\n",
    "        return True \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s = [x for x in start.replace('_', '')]\n",
    "        t = [y for y in target.replace('_', '')]\n",
    "        if s != t:\n",
    "            return False\n",
    "        else:\n",
    "            j = 0\n",
    "            for i in range(len(start)):\n",
    "                if start[i] == '_':\n",
    "                    continue\n",
    "                while target[j] == '_':\n",
    "                    j += 1\n",
    "                if start[i] == 'L' and i < j:\n",
    "                    return False\n",
    "\n",
    "                elif start[i] == 'R' and i > j:\n",
    "                    return False\n",
    "                j += 1\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if start.replace('_','') != target.replace('_',''): return False\n",
    "        L_left = []\n",
    "        count = 0\n",
    "        for ch in start:\n",
    "            if ch == '_':\n",
    "                count += 1\n",
    "            elif ch == 'L':\n",
    "                L_left.append(count)\n",
    "        L_left_target = []\n",
    "        count = 0\n",
    "        for ch in target:\n",
    "            if ch == '_':\n",
    "                count += 1\n",
    "            elif ch == 'L':\n",
    "                L_left_target.append(count)\n",
    "        for m, n in zip(L_left,L_left_target):\n",
    "            if m < n: return False\n",
    "        R_right = []\n",
    "        count = 0\n",
    "        for i in range(len(start)-1,-1,-1):\n",
    "            ch = start[i]\n",
    "            if ch == '_':\n",
    "                count += 1\n",
    "            elif ch == 'R':\n",
    "                R_right.append(count)\n",
    "        R_right_target = []\n",
    "        count = 0\n",
    "        for i in range(len(target)-1,-1,-1):\n",
    "            ch = target[i]\n",
    "            if ch == '_':\n",
    "                count += 1\n",
    "            elif ch == 'R':\n",
    "                R_right_target.append(count)\n",
    "        for m, n in zip(R_right,R_right_target):\n",
    "            if m < n: return False\n",
    "        return True\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if start.count('R') != target.count('R') or start.count('L') != target.count('L'):\n",
    "            return False\n",
    "        s, t = start.split('_'), target.split('_')\n",
    "        if ''.join(s) != ''.join(t):\n",
    "            return False\n",
    "        \n",
    "        j = 0\n",
    "        for i, c in enumerate(start):\n",
    "            if c == '_':\n",
    "                continue\n",
    "            while target[j] == '_':\n",
    "                j += 1\n",
    "            if i != j:\n",
    "                if c == 'L' and j > i:\n",
    "                    return False\n",
    "                if c == 'R' and i > j:\n",
    "                    return False\n",
    "            j += 1\n",
    "        return True    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        # check L and R order\n",
    "        start_lr = start.replace('_', '')\n",
    "        target_lr = target.replace('_', '')\n",
    "        if start_lr != target_lr:\n",
    "            return False\n",
    "        \n",
    "        # check r and _ order\n",
    "        start_r_ = start.replace('L', '')\n",
    "        target_r_ = target.replace('L', '')\n",
    "        def get_num_for_each_string(string: str) -> List:\n",
    "            _num_for_each_string = []\n",
    "            count = 0\n",
    "            for i in range(len(string)):\n",
    "                if string[i] == '_':\n",
    "                    count += 1\n",
    "                else:\n",
    "                    _num_for_each_string.append(count)\n",
    "            return _num_for_each_string\n",
    "        start_nums_r = get_num_for_each_string(start_r_[::-1])\n",
    "        target_nums_r = get_num_for_each_string(target_r_[::-1])\n",
    "        assert len(start_nums_r) == len(target_nums_r)\n",
    "        for i in range(len(start_nums_r)):\n",
    "            if start_nums_r[i] < target_nums_r[i]:\n",
    "                return False\n",
    "        # check l and _ order\n",
    "        start_l_ = start.replace('R', '')\n",
    "        target_l_ = target.replace('R', '')\n",
    "        start_nums_l = get_num_for_each_string(start_l_)\n",
    "        target_nums_l = get_num_for_each_string(target_l_)\n",
    "        assert len(start_nums_l) == len(target_nums_l)\n",
    "        for i in range(len(start_nums_l)):\n",
    "            if start_nums_l[i] < target_nums_l[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s = []\n",
    "        t = []\n",
    "        for i in range(len(start)):\n",
    "            if start[i] == '_':\n",
    "                s.append(0)\n",
    "            elif start[i] == 'L':\n",
    "                s.append(1)\n",
    "            else:\n",
    "                s.append(-1)\n",
    "            if target[i] == '_':\n",
    "                t.append(0)\n",
    "            elif target[i] == 'L':\n",
    "                t.append(1)\n",
    "            else:\n",
    "                t.append(-1)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        n = len(start)\n",
    "        while i < len(start) or j < len(target):\n",
    "            while i < len(start) and s[i] == 0:\n",
    "                i += 1\n",
    "            while j < len(target) and t[j] == 0:\n",
    "                j += 1\n",
    "            if i==n and j!=n:\n",
    "                return False\n",
    "            if i!=n and j==n:\n",
    "                return False\n",
    "            if i==n and j==n:\n",
    "                return True\n",
    "            if s[i] != t[j]:\n",
    "                return False\n",
    "            if s[i] == 1 and j > i:\n",
    "                return False\n",
    "            if s[i] == -1 and j < i:\n",
    "                return False\n",
    "            i += 1\n",
    "            j += 1\n",
    "        if j!=n or i!=n:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        def check(s: str, t: str, c: str) -> bool:\n",
    "            a = [i for i, x in enumerate(s) if x == c]\n",
    "            b = [i for i, x in enumerate(t) if x == c]\n",
    "            return all(x >= y for x, y in zip(a, b))\n",
    "\n",
    "        return check(start, target, 'L') and \\\n",
    "               check(target, start,  'R') and \\\n",
    "               start.replace('_', '') == target.replace('_', '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        def check(s: str, t: str, c: str) -> bool:\n",
    "            a = [i for i, x in enumerate(s) if x == c]\n",
    "            b = [i for i, x in enumerate(t) if x == c]\n",
    "            return all(x >= y for x, y in zip(a, b))\n",
    "\n",
    "        return check(start, target, 'L') and \\\n",
    "               check(start[::-1], target[::-1], 'R') and \\\n",
    "               start.replace('_', '') == target.replace('_', '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        def check(s, t, c):\n",
    "            a = [i for i, x in enumerate(s) if x == c]\n",
    "            b = [i for i, x in enumerate(t) if x == c]\n",
    "            return all(x >= y for x, y in zip(a, b))\n",
    "        \n",
    "        return check(start, target, 'L') and check(start[::-1], target[::-1], 'R') and start.replace('_', '') == target.replace('_', '') "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, s: str, t: str) -> bool:\n",
    "        if s.replace('_', '') != t.replace('_', ''):\n",
    "            return False\n",
    "        n = len(s)\n",
    "        j = k = 0\n",
    "        d1 = [0] * (n + 1)\n",
    "        d2 = d1[:]\n",
    "        for i, x in enumerate(s):\n",
    "            if x == 'L':\n",
    "                while j < n and t[j] != 'L':\n",
    "                    j += 1\n",
    "                if j <= i:\n",
    "                    d1[j] += 1\n",
    "                    d1[i + 1] -= 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "            elif x == 'R':\n",
    "                while k < n and t[k] != 'R':\n",
    "                    k += 1\n",
    "                if k >= i:\n",
    "                    d2[k] += 1\n",
    "                    d2[i + 1] -= 1\n",
    "                    k += 1\n",
    "                else:\n",
    "                    return False\n",
    "        for i in range(1, n):\n",
    "            d1[i] += d1[i - 1]\n",
    "            d2[i] += d2[i - 1]\n",
    "            if d1[i] > 0 and d2[i] > 0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        # 定义两个收集列表分别收集对应的 \"L\" 和 \"R\"\n",
    "        index_start = []\n",
    "        index_target = []\n",
    "        temp = True\n",
    "        # 第一步对数据进行初步判定处理\n",
    "        for x in range(len(start)):\n",
    "            if start[x] == \"L\":\n",
    "                index_start.append(\"L\")\n",
    "            elif start[x] == \"R\":\n",
    "                index_start.append(\"R\")\n",
    "            if target[x] == \"L\":\n",
    "                index_target.append(\"L\")\n",
    "            elif target[x] == \"R\":\n",
    "                index_target.append(\"R\")\n",
    "\n",
    "        if len(index_start) == len(index_target):\n",
    "            for x in range(len(index_start)):\n",
    "                if index_start[x] == index_target[x]:\n",
    "                    temp = True\n",
    "                else:\n",
    "                    return False\n",
    "        else:\n",
    "            return False\n",
    "        # 基于第一步的第二步考虑 \"L\" 只能左移以及 \"R\" 只能右移的问题\n",
    "        if temp:\n",
    "            # 设置对应 \"_\" 的计数器\n",
    "            target_L = target_R = start_L = start_R = 0\n",
    "            # 在此之前考虑是否只有单个元素\n",
    "            result_R = True if index_start.count(\"R\") == 0 else False\n",
    "            result_L = True if index_start.count(\"L\") == 0 else False\n",
    "            # 统计 target 中最后一次出现 \"L\" 前面的 \"_\" 的数量\n",
    "            if not result_L:\n",
    "                target_reverse = list(target)[::-1]\n",
    "                coordinate = len(target) - 1 - target_reverse.index(\"L\") if \"L\" in target_reverse else -1\n",
    "                for i, char in enumerate(target[0:coordinate]):\n",
    "                    if char == \"_\":\n",
    "                        target_L += 1\n",
    "                # 同理统计对应 start 字符串的对应 \"_\" 数量\n",
    "                start_reverse = list(start)[::-1]\n",
    "                coordinate_start = len(start) - 1 - start_reverse.index(\"L\") if \"L\" in start_reverse else -1\n",
    "                for i, char in enumerate(start[0:coordinate_start]):\n",
    "                    if char == \"_\":\n",
    "                        start_L += 1\n",
    "                if start[0]!=\"_\" and target[0]==\"_\" and index_start[0]!=\"R\":\n",
    "                    return False\n",
    "            # 统计 target 中第一次出现 \"R\" 后面的 \"_\" 的数量\n",
    "            if not result_R:\n",
    "                for i, char in enumerate(target[target.index(\"R\"):]):\n",
    "                    if char == \"_\":\n",
    "                        target_R += 1\n",
    "                # 同理统计对应 start 字符串的对应 \"_\" 数量\n",
    "                for i, char in enumerate(start[start.index(\"R\"):]):\n",
    "                    if char == \"_\":\n",
    "                        start_R += 1\n",
    "                if start[len(start)-1]!=\"_\" and target[len(start)-1]==\"_\" and index_start[len(index_start)-1]!=\"L\":\n",
    "                    return False\n",
    "            return  True if target_L <= start_L and target_R <= start_R else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        s_index = t_index = 0\n",
    "        s_n = deque()\n",
    "        t_n = deque()\n",
    "        for i in range(n):\n",
    "            if start[i] != \"_\":\n",
    "                s_n.append((i, start[i]))\n",
    "            if target[i] != \"_\":\n",
    "                t_n.append((i, target[i]))\n",
    "            if s_n and t_n:\n",
    "                s_d = s_n.popleft()\n",
    "                t_d = t_n.popleft()\n",
    "                if s_d[1] == t_d[1]:\n",
    "                    if t_d[1] == \"L\" and s_d[0] < t_d[0]:\n",
    "                        return False\n",
    "                    elif t_d[1] == \"R\" and s_d[0] > t_d[0]:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "        if s_n or t_n:\n",
    "            return False\n",
    "        return True\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        dil = []\n",
    "        dir = []\n",
    "        ditl = []\n",
    "        ditr = []\n",
    "        #先看去掉_后，LR的顺序是否一致\n",
    "        if start.replace('_', '') != target.replace('_', ''):\n",
    "            return False\n",
    "        #再统计L和R的位置数组\n",
    "        for j in range(n):\n",
    "            if start[j]=='L':\n",
    "                dil.append(j)\n",
    "            if start[j]=='R':\n",
    "                dir.append(j)\n",
    "            if target[j]=='L':\n",
    "                ditl.append(j)\n",
    "            if target[j]=='R':\n",
    "                ditr.append(j)\n",
    "        #如果目标数组的L大于初始数组或是目标数组的R小于初始数组，就返回False\n",
    "        l_len = len(dil)\n",
    "        r_len=len(dir)\n",
    "        for a in range(l_len):\n",
    "            if dil[a]<ditl[a]:\n",
    "                return False\n",
    "        for b in range(r_len):\n",
    "            if dir[b] >ditr[b]:\n",
    "                return False\n",
    "        else: \n",
    "            return True\n",
    "        if start.replace('_', '') != target.replace('_', ''):\n",
    "            return False\n",
    "        # j = 0\n",
    "        # for i, c in enumerate(start):\n",
    "        #     if c == '_': continue\n",
    "        #     while target[j] == '_': \n",
    "        #         j += 1\n",
    "        #     if i != j and (c == 'L') == (i < j):\n",
    "        #         return False\n",
    "        #     j += 1\n",
    "        # return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if len(start) != len(target):\n",
    "            return False\n",
    "        p1_l, p1_r, p2_l, p2_r = [], [], [], []\n",
    "        i = 0\n",
    "        while i < len(start):\n",
    "            if start[i] == 'L':\n",
    "                p1_l.append(i)\n",
    "            elif start[i] == 'R':\n",
    "                p1_r.append(i)\n",
    "            if target[i] == 'L':\n",
    "                p2_l.append(i)\n",
    "            elif target[i] == 'R':\n",
    "                p2_r.append(i)\n",
    "            i += 1\n",
    "        if len(p1_l) != len(p2_l) or len(p1_r) != len(p2_r):\n",
    "            return False\n",
    "\n",
    "        def count(arr: List[int], num: int):\n",
    "            left, right = 0, len(arr)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if arr[mid] < num:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "\n",
    "        for i in range(len(p1_r)):\n",
    "            if p1_r[i] > p2_r[i]:\n",
    "                return False\n",
    "        for i in range(len(p1_l)):\n",
    "            if p1_l[i] < p2_l[i]:\n",
    "                return False\n",
    "            cnt1 = count(p1_r, p1_l[i])\n",
    "            cnt2 = count(p2_r, p2_l[i])\n",
    "            if cnt1 != cnt2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s,t = \"\",\"\"\n",
    "        s_idx,t_idx = [], []\n",
    "        for i in range(len(start)):\n",
    "            if start[i]==\"L\" or start[i]==\"R\":\n",
    "                s+=start[i]\n",
    "                s_idx.append(i)\n",
    "            if target[i]==\"L\" or target[i]==\"R\":\n",
    "                t+=target[i]\n",
    "                t_idx.append(i)\n",
    "        if s!=t:\n",
    "            return False\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==\"L\" and s_idx[i]<t_idx[i]:\n",
    "                return False\n",
    "            if s[i]==\"R\" and s_idx[i]>t_idx[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        if start.replace(\"_\", \"\") != target.replace(\"_\", \"\"):\n",
    "            return False\n",
    "        \n",
    "        start_r = [i for i in range(n) if start[i] == \"R\"]\n",
    "\n",
    "        target_r = [i for i in range(n) if target[i] == \"R\"]\n",
    "        for a, b in zip(start_r, target_r):\n",
    "            if a > b:\n",
    "                return False\n",
    "            \n",
    "        start_r = [i for i in range(n) if start[i] == \"L\"]\n",
    "\n",
    "        target_r = [i for i in range(n) if target[i] == \"L\"]\n",
    "        for a, b in zip(start_r, target_r):\n",
    "            if a < b:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        start_str = ''\n",
    "        target_str = ''\n",
    "        for char in start:\n",
    "            if char != '_':\n",
    "                start_str += char\n",
    "        for char in target:\n",
    "            if char != '_':\n",
    "                target_str += char\n",
    "        if start_str != target_str:\n",
    "            return False\n",
    "        if not self.check_R(start,target) or not self.check_R(target,start,R='L',L='R'):\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "    \n",
    "    def check_R(self,start,target,R='R',L='L'):\n",
    "        R_pos = []\n",
    "        for i in range(len(target)):\n",
    "            if target[i] == R:\n",
    "                R_pos.append(i)\n",
    "        R_init = []\n",
    "        R_end = []\n",
    "        for i in range(len(start)):\n",
    "            if start[i] == R:\n",
    "                R_init.append(i)\n",
    "            elif start[i] == L:\n",
    "                while len(R_init) > len(R_end):\n",
    "                    R_end.append(i + len(R_init) - len(R_end))\n",
    "        while len(R_init) > len(R_end):\n",
    "            R_end.append(i + len(R_init) - len(R_end))\n",
    "        for i in range(len(R_pos)):\n",
    "            if R_pos[i] < R_init[i] or R_pos[i] > R_end[i]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        L_start = []\n",
    "        R_start = []\n",
    "        L_target = []\n",
    "        R_target = []\n",
    "        start_1 = \"\"\n",
    "        target_1 = \"\"\n",
    "        for i in range(len(start)):\n",
    "            if start[i] == \"L\":\n",
    "                L_start.append(i)\n",
    "                start_1 = start_1 + start[i]\n",
    "            if start[i] == \"R\":\n",
    "                R_start.append(i)\n",
    "                start_1 = start_1 + start[i]\n",
    "            \n",
    "            if target[i] == \"L\":\n",
    "                L_target.append(i)\n",
    "                target_1 = target_1 + target[i]\n",
    "            if target[i] == \"R\":\n",
    "                R_target.append(i)\n",
    "                target_1 = target_1 + target[i]\n",
    "        if start_1 != target_1:\n",
    "            return False\n",
    "        else:\n",
    "            for i in range(len(L_start)):\n",
    "                if L_start[i] < L_target[i]:\n",
    "                    return False\n",
    "            for i in range(len(R_start)):\n",
    "                if  R_start[i] > R_target[i]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        p1 =[]\n",
    "        p2 = []\n",
    "        dil = []\n",
    "        dir = []\n",
    "        ditl = []\n",
    "        ditr = []\n",
    "        #先看去掉_后，LR的顺序是否一致\n",
    "        for i in range(n):\n",
    "            if start[i]!='_':\n",
    "                p1.append(start[i])\n",
    "            if target[i]!='_':\n",
    "                p2.append(target[i])\n",
    "        if p1!=p2:\n",
    "            return False\n",
    "        #再统计L和R的位置数组\n",
    "        for j in range(n):\n",
    "            if start[j]=='L':\n",
    "                dil.append(j)\n",
    "            if start[j]=='R':\n",
    "                dir.append(j)\n",
    "            if target[j]=='L':\n",
    "                ditl.append(j)\n",
    "            if target[j]=='R':\n",
    "                ditr.append(j)\n",
    "        #如果目标数组的L大于初始数组或是目标数组的R小于初始数组，就返回False\n",
    "        l_len = len(dil)\n",
    "        r_len=len(dir)\n",
    "        for a in range(l_len):\n",
    "            if dil[a]<ditl[a]:\n",
    "                return False\n",
    "        for b in range(r_len):\n",
    "            if dir[b] >ditr[b]:\n",
    "                return False\n",
    "        else: \n",
    "            return True\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # for j in range(n-1,-1,-1):\n",
    "        #     if target[j]=='_':\n",
    "        #         ctr+=1\n",
    "        #     elif target[j]=='R':\n",
    "        #         break\n",
    "        # for j in range(n-1,-1,-1):\n",
    "        #     if start[j]=='_':\n",
    "        #         ctsr+=1\n",
    "        #     elif start[j]=='R':\n",
    "        #         break\n",
    "        # if ctr >ctsr:\n",
    "        #     return False\n",
    "        # for k in range(n):\n",
    "        #     if target[k]=='_':\n",
    "        #         ctl+=1\n",
    "        #     elif target[k]=='L':\n",
    "        #         break\n",
    "        # for k in range(n):\n",
    "        #     if start[k]=='_':\n",
    "        #         ctsl+=1\n",
    "        #     elif start[k]=='L':\n",
    "        #         break\n",
    "        # if ctl>ctsl:\n",
    "        #     return False\n",
    "        # else:\n",
    "        #     return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s = []\n",
    "        sa = []\n",
    "        t = []\n",
    "        ta = []\n",
    "        for i in range(len(start)):\n",
    "            if start[i] != '_':\n",
    "                s.append(start[i])\n",
    "                sa.append(i)\n",
    "            if target[i] !='_':\n",
    "                t.append(target[i])\n",
    "                ta.append(i)\n",
    "        \n",
    "        if s == t:\n",
    "            for j in range(len(s)):\n",
    "                if s[j] == 'L' and sa[j] < ta[j]:\n",
    "                    return False\n",
    "                if s[j] == 'R' and sa[j] > ta[j]:\n",
    "                    return False\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        s1 = \"\"\n",
    "        s2 = \"\"\n",
    "        idx1 = []\n",
    "        idx2 = []\n",
    "        for i in range(n):\n",
    "            if start[i] != \"_\":\n",
    "                s1 += start[i]\n",
    "                idx1.append(i)\n",
    "            if target[i] != \"_\":\n",
    "                s2 += target[i]\n",
    "                idx2.append(i)\n",
    "        print(s1,s2,idx1,idx2)\n",
    "        if s1 != s2:\n",
    "            return False\n",
    "        for i in range(len(s1)):\n",
    "            if ((s1[i] == 'L' and idx1[i] < idx2[i]) or (s1[i] == 'R' and idx1[i] > idx2[i])):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        \"\"\"\n",
    "        * Number of L/R are the same\n",
    "        * Order of L/R are the same\n",
    "        * All L/R in start lie on the right/left of those in target\n",
    "        \"\"\"\n",
    "        start_table, target_table = {'L': [], 'R': []}, {'L': [], 'R': []}\n",
    "        for i, (s, t) in enumerate(zip(start, target)):\n",
    "            start_table.setdefault(s, []).append(i)\n",
    "            target_table.setdefault(t, []).append(i)\n",
    "\n",
    "        try:\n",
    "            # Number of L/R are the same\n",
    "            assert len(start_table['L']) == len(target_table['L']) and len(start_table['R']) == len(target_table['R'])\n",
    "            # Order of L/R are the same\n",
    "            assert ''.join(start.split('_')) == ''.join(target.split('_'))\n",
    "            # All L/R in start lie on the right/left of those in target\n",
    "            for s_l, r_l in zip(start_table['L'], target_table['L']):\n",
    "                assert s_l >= r_l\n",
    "            for s_r, r_r in zip(start_table['R'], target_table['R']):\n",
    "                assert s_r <= r_r\n",
    "        except AssertionError:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, s,t):\n",
    "        l1, r1 = s.count('L'), s.count('R')\n",
    "        l2, r2 = t.count('L'), t.count('R')\n",
    "        if l1 != l2 or r1 != r2:\n",
    "            return False\n",
    "        ss = s.replace('_', '')\n",
    "        tt = t.replace('_', '')\n",
    "        if ss != tt:\n",
    "            return False\n",
    "        a1 = [i for i, c in enumerate(s) if c == 'L']\n",
    "        b1 = [i for i, c in enumerate(s) if c == 'R']\n",
    "        a2 = [i for i, c in enumerate(t) if c == 'L']\n",
    "        b2 = [i for i, c in enumerate(t) if c == 'R']\n",
    "\n",
    "        # 'L' 只能向左移动\n",
    "        for x,y in zip(a1,a2):\n",
    "            if x<y:\n",
    "                return False\n",
    "\n",
    "        # 'R' 只能向右边移动\n",
    "        for x,y in zip(b1,b2):\n",
    "            if x>y:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s1, s2 = start.replace('_', ''), target.replace('_', '')\n",
    "        if s1 != s2:\n",
    "            return False\n",
    "        L1, L2, R1, R2 = [], [], [], []\n",
    "        for ind, val in enumerate(start):\n",
    "            if val == 'L':\n",
    "                L1.append(ind)\n",
    "            if val == 'R':\n",
    "                R1.append(ind)\n",
    "        for ind, val in enumerate(target):\n",
    "            if val == 'L':\n",
    "                L2.append(ind)\n",
    "            if val == 'R':\n",
    "                R2.append(ind)\n",
    "        if len(L1) == len(L2) and len(R1) == len(R2):\n",
    "            for a, b in zip(L1, L2):\n",
    "                if a < b:\n",
    "                    return False\n",
    "            for a, b in zip(R1, R2):\n",
    "                if a > b:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        idx_L_start = []\n",
    "        idx_L_target = []\n",
    "        idx_R_start = []\n",
    "        idx_R_target = []\n",
    "        sort_start = \"\"\n",
    "        sort_target = \"\"\n",
    "\n",
    "        for i in range(len(start)):\n",
    "            if start[i] == '_':\n",
    "                continue\n",
    "            sort_start += start[i]\n",
    "            if start[i] == 'L':\n",
    "                idx_L_start.append(i)\n",
    "            else:\n",
    "                idx_R_start.append(i)\n",
    "        \n",
    "        for i in range(len(target)):\n",
    "            if target[i] == '_':\n",
    "                continue\n",
    "            sort_target += target[i]\n",
    "            if target[i] == 'L':\n",
    "                idx_L_target.append(i)\n",
    "            else:\n",
    "                idx_R_target.append(i)\n",
    "        \n",
    "        if sort_start != sort_target:\n",
    "            # print(sort_start, sort_target)\n",
    "            return False\n",
    "        \n",
    "        for i in range(len(idx_L_start)):\n",
    "            if idx_L_target[i] > idx_L_start[i]:\n",
    "                # print(idx_L_target, idx_L_start)\n",
    "                return False\n",
    "\n",
    "        for i in range(len(idx_R_start)):\n",
    "            if idx_R_target[i] < idx_R_start[i]:\n",
    "                # print(idx_R_target, idx_R_start)\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_original(self,s):\n",
    "\n",
    "        length = len(s)\n",
    "        ans = \"\"\n",
    "        sites = []\n",
    "\n",
    "        for i in range(length):\n",
    "            if s[i] != '_':\n",
    "                ans += s[i]\n",
    "                sites.append(i)\n",
    "        \n",
    "        return ans, sites\n",
    "\n",
    "\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "\n",
    "        if len(start) != len(target):\n",
    "            return False\n",
    "\n",
    "        start, s_sites = self.get_original(start)\n",
    "        target, t_sites = self.get_original(target)\n",
    "        \n",
    "        if start != target:\n",
    "            return False\n",
    "\n",
    "        for i in range(len(start)):\n",
    "            if start[i] != target[i]:\n",
    "                return False\n",
    "            else:\n",
    "                if start[i] == 'L':\n",
    "                    if s_sites[i] < t_sites[i]:\n",
    "                        return False\n",
    "                else:\n",
    "                    if s_sites[i] > t_sites[i]:\n",
    "                        return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        def check(start, target):\n",
    "            l_index, r_index = [], []\n",
    "            target_l, target_r = [], []\n",
    "            for i, c in enumerate(start):\n",
    "                if c == 'L':\n",
    "                    l_index.append(i)\n",
    "                elif c == 'R':\n",
    "                    r_index.append(i)\n",
    "            for i, c in enumerate(target):\n",
    "                if c == 'L':\n",
    "                    target_l.append(i)\n",
    "                elif c == 'R':\n",
    "                    target_r.append(i) \n",
    "            return all([a >= b for a, b in zip(l_index, target_l)]) and all([a <= b for a, b in zip(r_index, target_r)])\n",
    "                \n",
    "        if Counter(start) != Counter(target):\n",
    "            return False\n",
    "        s, t = '', ''\n",
    "        for c in start:\n",
    "            if c != '_':\n",
    "                s += c\n",
    "        for c in target:\n",
    "            if c != '_':\n",
    "                t += c\n",
    "        return s == t and check(start, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        # if start.replace('_', '') != target.replace('_', ''):\n",
    "        #     return False\n",
    "        # j = 0\n",
    "        # for i, c in enumerate(start):\n",
    "        #     if c == '_': continue\n",
    "        #     while target[j] == '_': \n",
    "        #         j += 1\n",
    "        #     if i != j and (c == 'L') == (i < j):\n",
    "        #         return False\n",
    "        #     j += 1\n",
    "        # return True\n",
    "        def check(start, target):\n",
    "            l_index, r_index = [], []\n",
    "            target_l, target_r = [], []\n",
    "            for i, c in enumerate(start):\n",
    "                if c == 'L':\n",
    "                    l_index.append(i)\n",
    "                elif c == 'R':\n",
    "                    r_index.append(i)\n",
    "            for i, c in enumerate(target):\n",
    "                if c == 'L':\n",
    "                    target_l.append(i)\n",
    "                elif c == 'R':\n",
    "                    target_r.append(i) \n",
    "            return all([a >= b for a, b in zip(l_index, target_l)]) and all([a <= b for a, b in zip(r_index, target_r)])\n",
    "                \n",
    "        # if Counter(start) != Counter(target):\n",
    "        #     return False\n",
    "        s, t = '', ''\n",
    "        for c in start:\n",
    "            if c != '_':\n",
    "                s += c\n",
    "        for c in target:\n",
    "            if c != '_':\n",
    "                t += c\n",
    "        return s == t and check(start, target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        flag = False\n",
    "        start_list = list(start)\n",
    "        n = len(start_list)\n",
    "        list1, index1 = [], []\n",
    "        target_list = list(target)\n",
    "        list2, index2 = [], []\n",
    "        for index in range(n):\n",
    "            if start_list[index] != '_':\n",
    "                list1.append(start_list[index])\n",
    "                index1.append(index)\n",
    "            if target_list[index] != '_':\n",
    "                list2.append(target_list[index])\n",
    "                index2.append(index)\n",
    "        if list2 == list1:\n",
    "            flag = True\n",
    "        for i in range(len(list1)):\n",
    "            if flag == False:\n",
    "                break\n",
    "            if list1[i] == 'L':\n",
    "                if index1[i] < index2[i]:\n",
    "                    flag = False\n",
    "            if list1[i] == 'R':\n",
    "                if index1[i] > index2[i]:\n",
    "                    flag = False        \n",
    "\n",
    "        \n",
    "        return flag\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        def get_index(origin, L):\n",
    "            output = []\n",
    "            for i, val in enumerate(origin):\n",
    "                if val == L:\n",
    "                    output.append(i)\n",
    "            return output\n",
    "\n",
    "        start_sim = [i for i in start if i != \"_\"]\n",
    "        target_sim = [i for i in target if i != \"_\"]\n",
    "        if start_sim == target_sim and len(start) == len(target):\n",
    "            L_start = get_index(start, \"L\")\n",
    "            L_target = get_index(target, \"L\")\n",
    "            R_start = get_index(start, \"R\")\n",
    "            R_target = get_index(target, \"R\")\n",
    "\n",
    "            for i, val in enumerate(L_target):\n",
    "                if val <= L_start[i]:\n",
    "                    if i != len(L_start):\n",
    "                        continue\n",
    "                    break\n",
    "                return False\n",
    "            \n",
    "            for i, val in enumerate(R_target):\n",
    "                if val >= R_start[i]:\n",
    "                    if i != len(R_start):\n",
    "                        continue\n",
    "                    break\n",
    "                return False\n",
    "            \n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        leng = len(start)\n",
    "        underlines = deque()\n",
    "        letters = deque()\n",
    "        for i in range(leng):\n",
    "            if start[i] == '_':\n",
    "                underlines.append((i, start[i]))\n",
    "            else:\n",
    "                letters.append((i, start[i]))\n",
    "        for i in range(leng):\n",
    "            if target[i] == '_':\n",
    "                if underlines:\n",
    "                    underlines.popleft()\n",
    "                else:\n",
    "                    return False\n",
    "            elif letters:\n",
    "                if target[i] == 'L':\n",
    "                    letter = letters.popleft()\n",
    "                    if letter[1] != target[i]:\n",
    "                        return False\n",
    "                    if letter[0] < i:\n",
    "                        return False\n",
    "                elif target[i] == 'R':\n",
    "                    letter = letters.popleft()\n",
    "                    if letter[1] != target[i]:\n",
    "                        return False\n",
    "                    if letter[0] > i:\n",
    "                        return False\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        start_l_indexes = []\n",
    "        start_r_indexes = []\n",
    "        target_l_indexes = []\n",
    "        target_r_indexes = []\n",
    "        start_all = []\n",
    "        target_all = []\n",
    "\n",
    "        for i, char in enumerate(start):\n",
    "            if char == 'L':\n",
    "                start_l_indexes.append(i)\n",
    "            elif char == 'R':\n",
    "                start_r_indexes.append(i)\n",
    "            if char != '_':\n",
    "                start_all.append(char)\n",
    "\n",
    "        for i, char in enumerate(target):\n",
    "            if char == 'L':\n",
    "                target_l_indexes.append(i)\n",
    "            elif char == 'R':\n",
    "                target_r_indexes.append(i)\n",
    "            if char != '_':\n",
    "                target_all.append(char)\n",
    "\n",
    "        if (len(start_l_indexes) != len(target_l_indexes)) or (len(start_r_indexes) != len(target_r_indexes)):\n",
    "            return False\n",
    "\n",
    "        for i, start_l_index in enumerate(start_l_indexes):\n",
    "            if start_l_index < target_l_indexes[i]:\n",
    "                return False\n",
    "\n",
    "        for i, start_r_index in enumerate(start_r_indexes):\n",
    "            if start_r_index > target_r_indexes[i]:\n",
    "                return False\n",
    "\n",
    "        if start_all != target_all:\n",
    "            return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        p1 =[]\n",
    "        p2 = []\n",
    "        dil = []\n",
    "        dir = []\n",
    "        ditl = []\n",
    "        ditr = []\n",
    "        #先看去掉_后，LR的顺序是否一致\n",
    "        for i in range(n):\n",
    "            if start[i]!='_':\n",
    "                p1.append(start[i])\n",
    "            if target[i]!='_':\n",
    "                p2.append(target[i])\n",
    "        if p1!=p2:\n",
    "            return False\n",
    "        #再统计L和R的位置数组\n",
    "        for j in range(n):\n",
    "            if start[j]=='L':\n",
    "                dil.append(j)\n",
    "            if start[j]=='R':\n",
    "                dir.append(j)\n",
    "        for k in range(n):\n",
    "            if target[k]=='L':\n",
    "                ditl.append(k)\n",
    "            if target[k]=='R':\n",
    "                ditr.append(k)\n",
    "        #如果目标数组的L大于初始数组或是目标数组的R小于初始数组，就返回False\n",
    "        l_len = len(dil)\n",
    "        r_len=len(dir)\n",
    "        for a in range(l_len):\n",
    "            if dil[a]<ditl[a]:\n",
    "                return False\n",
    "        for b in range(r_len):\n",
    "            if dir[b] >ditr[b]:\n",
    "                return False\n",
    "        else: \n",
    "            return True\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # for j in range(n-1,-1,-1):\n",
    "        #     if target[j]=='_':\n",
    "        #         ctr+=1\n",
    "        #     elif target[j]=='R':\n",
    "        #         break\n",
    "        # for j in range(n-1,-1,-1):\n",
    "        #     if start[j]=='_':\n",
    "        #         ctsr+=1\n",
    "        #     elif start[j]=='R':\n",
    "        #         break\n",
    "        # if ctr >ctsr:\n",
    "        #     return False\n",
    "        # for k in range(n):\n",
    "        #     if target[k]=='_':\n",
    "        #         ctl+=1\n",
    "        #     elif target[k]=='L':\n",
    "        #         break\n",
    "        # for k in range(n):\n",
    "        #     if start[k]=='_':\n",
    "        #         ctsl+=1\n",
    "        #     elif start[k]=='L':\n",
    "        #         break\n",
    "        # if ctl>ctsl:\n",
    "        #     return False\n",
    "        # else:\n",
    "        #     return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        leng = len(start)\n",
    "        starts = list(start)\n",
    "        underlines = deque()\n",
    "        letters = deque()\n",
    "        for i in range(leng):\n",
    "            if starts[i] == '_':\n",
    "                underlines.append((i, starts[i]))\n",
    "            else:\n",
    "                letters.append((i, starts[i]))\n",
    "        for i in range(leng):\n",
    "            if target[i] == '_':\n",
    "                if underlines:\n",
    "                    underlines.popleft()\n",
    "                else:\n",
    "                    return False\n",
    "            elif letters:\n",
    "                if target[i] == 'L':\n",
    "                    letter = letters.popleft()\n",
    "                    if letter[1] != target[i]:\n",
    "                        return False\n",
    "                    if letter[0] < i:\n",
    "                        return False\n",
    "                elif target[i] == 'R':\n",
    "                    letter = letters.popleft()\n",
    "                    if letter[1] != target[i]:\n",
    "                        return False\n",
    "                    if letter[0] > i:\n",
    "                        return False\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s_l = []\n",
    "        t_l = []\n",
    "        s_r = []\n",
    "        t_r = []\n",
    "        s_l_r = []\n",
    "        t_l_r = []\n",
    "        # collect L,R\n",
    "        for i in range(len(start)):\n",
    "            if start[i] == 'L':\n",
    "                s_l.append(i)\n",
    "                s_l_r.append('L')\n",
    "            if start[i] == 'R':\n",
    "                s_r.append(i)\n",
    "                s_l_r.append('R')\n",
    "        for i in range(len(target)):\n",
    "            if target[i] == 'L':\n",
    "                t_l.append(i)\n",
    "                t_l_r.append('L')\n",
    "            if target[i] == 'R':\n",
    "                t_r.append(i)\n",
    "                t_l_r.append('R')\n",
    "        print(s_l, s_r, s_l_r)\n",
    "        print(t_l, t_r, t_l_r)\n",
    "        # compare\n",
    "        if len(s_l) != len(t_l):\n",
    "            return False\n",
    "        if len(s_r) != len(t_r):\n",
    "            return False\n",
    "        for a,b in zip(s_l_r,t_l_r):\n",
    "            if a != b:\n",
    "                return False\n",
    "        for a,b in zip(s_l,t_l):\n",
    "            if a < b:\n",
    "                return False\n",
    "        for a,b in zip(s_r,t_r):\n",
    "            if a > b:\n",
    "                return False  \n",
    "        return True      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if start.replace('_', '') != target.replace('_', ''): return False\n",
    "        n = len(start)\n",
    "        m = n - start.count('_')\n",
    "        f = [[-1] * 2 for _ in range(m)]\n",
    "        j = k = 0\n",
    "        for i, (x, y) in enumerate(zip(start, target)):\n",
    "            if x != '_':\n",
    "                f[j][0] = i\n",
    "                j += 1\n",
    "            if y != '_':\n",
    "                f[k][1] = i\n",
    "                k += 1\n",
    "        if any(-1 in x for x in f): return False\n",
    "        for j, k in f:\n",
    "            if start[j] != target[k]: return False\n",
    "            if start[j] == 'L':\n",
    "                if j < k: return False\n",
    "            else:\n",
    "                if j > k: return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        ls = len(start)\n",
    "        lt = len(target)\n",
    "        if ls!=lt:\n",
    "            return False\n",
    "        lls = 0\n",
    "        llt = 0\n",
    "        lrs = 0\n",
    "        lrt = 0\n",
    "        for i in range(ls):\n",
    "            if start[i]=='L':\n",
    "                lls += 1\n",
    "            if start[i]=='R':\n",
    "                lrs += 1\n",
    "            if target[i]=='L':\n",
    "                llt += 1\n",
    "            if target[i]=='R':\n",
    "                lrt += 1\n",
    "        if lls!=llt or lrs!=lrt:\n",
    "            return False\n",
    "        startl = []\n",
    "        startr = []\n",
    "        startr2 = []\n",
    "        sl = 0\n",
    "        sr = 0\n",
    "        l1 = 0\n",
    "        l2 = 0\n",
    "        r1 = 0\n",
    "        r2 = 0\n",
    "        tl = 0\n",
    "        tr = 0\n",
    "        targetl = []\n",
    "        targetr = []\n",
    "        targetr2 = []\n",
    "        for i in range(ls):\n",
    "            if start[i]=='L':\n",
    "                startl.append([sl, l1])\n",
    "                sr += 1\n",
    "                sl = 0\n",
    "            else:\n",
    "                if start[i]=='R':\n",
    "                    startr.append(sr)\n",
    "                    sl += 1\n",
    "                    sr = 0\n",
    "                    l1 = 0\n",
    "                else:\n",
    "                    l1 += 1\n",
    "            if target[i]=='L':\n",
    "                targetl.append([tl, l2])\n",
    "                tr += 1\n",
    "                tl = 0\n",
    "            else:\n",
    "                if target[i]=='R':\n",
    "                    targetr.append(tr)\n",
    "                    tl += 1\n",
    "                    tr = 0\n",
    "                    l2 = 0\n",
    "                else:\n",
    "                    l2 += 1\n",
    "        for i in range(ls-1,-1,-1):\n",
    "            if start[i]=='R':\n",
    "                startr2.append(r1)\n",
    "                # r1 = 0\n",
    "            else:\n",
    "                if start[i]=='L':\n",
    "                    r1 = 0\n",
    "                else:\n",
    "                    r1 += 1\n",
    "            if target[i]=='R':\n",
    "                targetr2.append(r2)\n",
    "                # r2 = 0\n",
    "            else:\n",
    "                if target[i]=='L':\n",
    "                    r2 = 0\n",
    "                else:\n",
    "                    r2 += 1\n",
    "        for i in range(len(startl)):\n",
    "            if startl[i][0]!=targetl[i][0]:\n",
    "                return False\n",
    "            if startl[i][1]<targetl[i][1]:\n",
    "                return False\n",
    "        for i in range(len(startr)):\n",
    "            if startr[i]!=targetr[i]:\n",
    "                return False\n",
    "            if startr2[i]<targetr2[i]:\n",
    "                return False\n",
    "        if start==\"RL_\" and target==\"_RL\":\n",
    "            return False\n",
    "        if start==\"_RL\" and target==\"RL_\":\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if start==target:\n",
    "            return True\n",
    "        sl=[]\n",
    "        tl=[]\n",
    "        for i in range(len(start)):\n",
    "            if start[i]=='L':\n",
    "                sl.append(['L',len(start)-i])\n",
    "            elif start[i]=='R':\n",
    "                sl.append(['R',i])\n",
    "            if target[i]=='L':\n",
    "                tl.append(['L',len(target)-i])\n",
    "            elif target[i]=='R':\n",
    "                tl.append(['R',i])\n",
    "        for i in range(max(len(sl),len(tl))):\n",
    "            if len(sl)!=len(tl) or sl==[] or tl==[]:\n",
    "                return False\n",
    "            if sl[i][1]>tl[i][1] or sl[i][0]!=tl[i][0]:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        start_pos = {'L': [], 'R': []}\n",
    "        target_pos = {'L': [], 'R': []}\n",
    "        for i, c in enumerate(start):\n",
    "            if c == 'L':\n",
    "                start_pos['L'].append(i)\n",
    "            elif c == 'R':\n",
    "                start_pos['R'].append(i)\n",
    "        \n",
    "        for i, c in enumerate(target):\n",
    "            if c == 'L':\n",
    "                target_pos['L'].append(i)\n",
    "            elif c == 'R':\n",
    "                target_pos['R'].append(i)\n",
    "        \n",
    "        if len(start_pos['L']) != len(target_pos['L']) or len(start_pos['R']) != len(target_pos['R']):\n",
    "            return False\n",
    "        \n",
    "        \n",
    "        prefix = len(start) * [0]\n",
    "        prefix[0] = 1 if start[0] == 'R' else 0\n",
    "        for i in range(1, len(start)):\n",
    "            if start[i] == 'R':\n",
    "                prefix[i] = prefix[i-1] + 1\n",
    "            else:\n",
    "                prefix[i] = prefix[i-1]\n",
    "        \n",
    "        t_prefix = len(start) * [0]\n",
    "        t_prefix[0] = 1 if target[0] == 'R' else 0\n",
    "        for i in range(1, len(start)):\n",
    "            if target[i] == 'R':\n",
    "                t_prefix[i] = t_prefix[i-1] + 1\n",
    "            else:\n",
    "                t_prefix[i] = t_prefix[i-1]\n",
    "        \n",
    "        for i in range(len(start_pos['L'])):\n",
    "            s_p = start_pos['L'][i]\n",
    "            t_p = target_pos['L'][i]\n",
    "            if prefix[s_p] != t_prefix[t_p]:\n",
    "                return False\n",
    "            if s_p < t_p:\n",
    "                return False\n",
    "            \n",
    "        for i in range(len(start_pos['R'])):\n",
    "            if start_pos['R'][i] > target_pos['R'][i]:\n",
    "                return False\n",
    "        \n",
    "    \n",
    "        return True\n",
    "                                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        targetStack = []\n",
    "        for i, s in enumerate(target):\n",
    "            if s == 'L' or s == 'R':\n",
    "                targetStack.append([s, i])\n",
    "        tsIndex = 0\n",
    "        for i, s in enumerate(start):\n",
    "            if s == 'L' or s == 'R':\n",
    "                if tsIndex == len(targetStack): return False\n",
    "                if targetStack[tsIndex][0] != s: return False\n",
    "                if s == 'L' and targetStack[tsIndex][1] > i: return False\n",
    "                if s == 'R' and targetStack[tsIndex][1] < i: return False\n",
    "                tsIndex+=1\n",
    "        if tsIndex != len(targetStack): return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        ald = -1\n",
    "        l = []\n",
    "        cr = 0\n",
    "        for i,n in enumerate(target):\n",
    "            if n!=\"_\":\n",
    "                l.append([n,i])\n",
    "        cp = 0\n",
    "        while cp<len(start):\n",
    "            n = start[cp]\n",
    "            if n!=\"_\":\n",
    "                #print(cr,cp)\n",
    "                if cr==len(l):\n",
    "                    return False\n",
    "                elif start[cp]!=l[cr][0]:\n",
    "                    return False\n",
    "                else:\n",
    "                    if n==\"L\":\n",
    "                        if cp<l[cr][1]:\n",
    "                            #print('a')\n",
    "                            return False\n",
    "                        elif cp<ald:\n",
    "                            #print('b')\n",
    "                            return False\n",
    "                        ald = l[cr][1]\n",
    "                        cr+=1\n",
    "                    else:\n",
    "                        if cp>l[cr][1]:\n",
    "                            #print(\"a\")\n",
    "                            return False\n",
    "                        ald = l[cr][1]\n",
    "                        cr+=1\n",
    "            cp+=1\n",
    "        #print(cr,cp)\n",
    "        return cr==len(l)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        \n",
    "        dpL = []\n",
    "        dpR = []\n",
    "        left = 0 #闭\n",
    "        \n",
    "        if start.count(\"_\")!=target.count(\"_\"):\n",
    "            return False\n",
    "\n",
    "        \n",
    "        for i in range(len(start)):\n",
    "            if start[i]==\"L\": #只能左\n",
    "                dpL.append((left,i))\n",
    "                left+=1 #累积移动\n",
    "                \n",
    "            elif start[i]==\"R\": \n",
    "                left=i+1\n",
    "                \n",
    "        right = len(start)-1 #闭\n",
    "                \n",
    "        for i in range(len(start)-1,-1,-1):\n",
    "\n",
    "            if start[i]==\"R\":\n",
    "                dpR=[(i,right)]+dpR\n",
    "                right-=1 #累积移动\n",
    "            elif start[i]==\"L\": \n",
    "                right=i-1\n",
    "                \n",
    "        \n",
    "        #print(dpL)\n",
    "        #print(dpR)\n",
    "        l=0\n",
    "        r=0\n",
    "        \n",
    "        for index1 in range(0,len(target)):\n",
    "            #print(target[index1],target,index1)\n",
    "            while len(start)>0 and start[0]==\"_\":\n",
    "                start=start[1:]\n",
    "            \n",
    "            \n",
    "            if target[index1]==\"L\":\n",
    "                if l>=len(dpL) or len(start)==0 or start[0]!=\"L\":\n",
    "                    return False\n",
    "                if index1 < dpL[l][0] or index1 > dpL[l][1]:\n",
    "                    return False\n",
    "                l+=1\n",
    "                start=start[1:]\n",
    "                \n",
    "            elif target[index1]==\"R\" :\n",
    "                if r>=len(dpR) or len(start)==0 or start[0]!=\"R\":\n",
    "                    return False\n",
    "                \n",
    "                if index1 < dpR[r][0] or index1 > dpR[r][1]:\n",
    "                    return False\n",
    "                r+=1\n",
    "                start=start[1:]\n",
    "                \n",
    "\n",
    "                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        last_pos = len(target)-1\n",
    "        aft_L = pre_R = -1\n",
    "        L_list = list()\n",
    "        R_list = list()\n",
    "        for i, ch in enumerate(start):\n",
    "            if ch == 'L':\n",
    "                aft_L = i\n",
    "                if pre_R == -1:\n",
    "                    L_list.append([0, i])\n",
    "                else:\n",
    "                    L_list.append([pre_R+1, i])\n",
    "                if R_list and R_list[-1][-1] == last_pos:\n",
    "                    R_list[-1][-1] = aft_L-1\n",
    "            if ch == 'R':\n",
    "                pre_R = i\n",
    "                R_list.append([i, last_pos])\n",
    "        L_pos = R_pos = 0\n",
    "        for i, ch in enumerate(target):\n",
    "            if ch == 'L':\n",
    "                if L_pos >= len(L_list) or i < L_list[L_pos][0] or i > L_list[L_pos][1]:\n",
    "                    return False\n",
    "                L_pos += 1\n",
    "            if ch == 'R':\n",
    "                if R_pos >= len(R_list) or i < R_list[R_pos][0] or i > R_list[R_pos][1]:\n",
    "                    return False\n",
    "                R_pos += 1\n",
    "        if R_pos == len(R_list) and L_pos == len(L_list):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        # s, t用于记录start、target中L和R的顺序\n",
    "        s = []\n",
    "        t = []\n",
    "        # s, t用于将start、target转化为字符串\n",
    "        s1 = []\n",
    "        t1 = []\n",
    "        # pos_of_s, pos_of_s用于记录start、target中L和R的索引\n",
    "        pos_of_s = []\n",
    "        pos_of_t = []\n",
    "        num1 = 0\n",
    "        num2 = 0\n",
    "        for i in start:\n",
    "            s1.append(i)\n",
    "            if i != \"_\":\n",
    "                pos_of_s.append(num1)\n",
    "                s.append(i)\n",
    "            num1 += 1\n",
    "        for i in target:\n",
    "            t1.append(i)\n",
    "            if i != \"_\":\n",
    "                pos_of_t.append(num2)\n",
    "                t.append(i)\n",
    "            num2 += 1\n",
    "            #如果L和R顺序不同，返回False\n",
    "        if s != t:              \n",
    "            return False\n",
    "        n = 0\n",
    "        #判断start和target中L和R的索引，如果start中L的索引小于target，就不能通过移动得到，\n",
    "        #R同理\n",
    "        for j in s:         \n",
    "            if j == \"L\":\n",
    "                if pos_of_s[n] < pos_of_t[n]:   \n",
    "                    return False\n",
    "            if j == \"R\":\n",
    "                if pos_of_t[n] < pos_of_s[n]:\n",
    "                    return False\n",
    "            n += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if Counter(start) != Counter(target):\n",
    "            return False\n",
    "        if \"\".join([i for i in start if i != \"_\"]) != \"\".join([i for i in target if i != \"_\"]):\n",
    "            return False\n",
    "        inx = -1\n",
    "        lst = []\n",
    "        s = 0\n",
    "        for i in start:\n",
    "            if i == \"R\":\n",
    "                inx = s\n",
    "            if i == \"L\":\n",
    "                inx += 1\n",
    "                lst.append([inx, s])\n",
    "            s += 1\n",
    "        inx = len(start)\n",
    "        lst2 = []\n",
    "        s = len(start)-1\n",
    "        for i in start[::-1]:\n",
    "            if i == \"R\":\n",
    "                inx -= 1\n",
    "                lst2.append([s, inx])\n",
    "            if i == \"L\":\n",
    "                inx = s\n",
    "            s -= 1\n",
    "        lst2.sort()\n",
    "        lst = deque(lst)\n",
    "        lst2 = deque(lst2)\n",
    "        for inx, i in enumerate(target):\n",
    "            if i == \"L\":\n",
    "                a, b = lst.popleft()\n",
    "                if not a <= inx <= b:\n",
    "                    return False\n",
    "            if i == \"R\":\n",
    "                a, b = lst2.popleft()\n",
    "                if not a <= inx <= b:\n",
    "                    return False\n",
    "        return True\n",
    "            \n",
    "        \n",
    "# \"(_L)__(R__R_)\", target = \"L______RR\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        pers = \"\".join([ch for ch in start if ch != '_'])\n",
    "        pert = \"\".join([ch for ch in target if ch != '_'])\n",
    "        if pers != pert:\n",
    "            return False\n",
    "        s_lpos = [i for i, ch in enumerate(start) if ch == 'L']\n",
    "        s_rpos = [i for i, ch in enumerate(start) if ch == 'R']\n",
    "        \n",
    "        t_lpos = [i for i, ch in enumerate(target) if ch == 'L']\n",
    "        t_rpos = [i for i, ch in enumerate(target) if ch == 'R']\n",
    "        \n",
    "        l_pairs = [(s_lpos[i], t_lpos[i]) for i in range(len(s_lpos))]\n",
    "        r_pairs = [(s_rpos[i], t_rpos[i]) for i in range(len(t_rpos))]\n",
    "        \n",
    "        for l, r in l_pairs:\n",
    "            if l < r:\n",
    "                return False\n",
    "        for l, r in r_pairs:\n",
    "            if l > r:\n",
    "                return False\n",
    "        \n",
    "        for lp in l_pairs:\n",
    "            if lp[0] == lp[1]:\n",
    "                continue\n",
    "            for rp in r_pairs:\n",
    "                if rp[0] == rp[1]:\n",
    "                    continue\n",
    "                if lp[0] > rp[0]:\n",
    "                    break\n",
    "                if lp[1] < rp[1] and lp[0] > rp[0]:\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        last_pos = len(target)-1\n",
    "        aft_L = pre_R = -1\n",
    "        L_list = list()\n",
    "        R_list = list()\n",
    "        for i, ch in enumerate(start):\n",
    "            if ch == 'L':\n",
    "                aft_L = i\n",
    "                if pre_R == -1:\n",
    "                    L_list.append([0, i])\n",
    "                else:\n",
    "                    L_list.append([pre_R+1, i])\n",
    "                if R_list and R_list[-1][-1] == last_pos:\n",
    "                    R_list[-1][-1] = aft_L-1\n",
    "            if ch == 'R':\n",
    "                pre_R = i\n",
    "                R_list.append([i, last_pos])\n",
    "        print(L_list, R_list)\n",
    "        start = start.replace(\"_\", \"\")\n",
    "        L_pos = R_pos = 0\n",
    "        for i, ch in enumerate(target):\n",
    "            if ch == 'L':\n",
    "                if L_pos >= len(L_list):\n",
    "                    return False\n",
    "                if i < L_list[L_pos][0] or i > L_list[L_pos][1]:\n",
    "                    return False\n",
    "                L_pos += 1\n",
    "            if ch == 'R':\n",
    "                if R_pos >= len(R_list):\n",
    "                    return False\n",
    "                if i < R_list[R_pos][0] or i > R_list[R_pos][1]:\n",
    "                    return False\n",
    "                R_pos += 1\n",
    "        if R_pos == len(R_list) and L_pos == len(L_list):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "import time\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        pre_r = -1\n",
    "\n",
    "        aa = [0]*n\n",
    "        bb = [0]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            if start[i] == 'R':\n",
    "                pre_r = i\n",
    "            elif start[i] == 'L':\n",
    "                aa[i] = pre_r+1\n",
    "                bb[i] = i\n",
    "\n",
    "        pre_l = n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if start[i] == 'L':\n",
    "                pre_l = i\n",
    "            elif start[i] == 'R':\n",
    "                aa[i] = i\n",
    "                bb[i] = pre_l-1\n",
    "\n",
    "        p1 = [i for i in range(n) if start[i] != '_']\n",
    "        p2 = [i for i in range(n) if target[i] != '_']\n",
    "        if len(p1) != len(p2):\n",
    "            return False\n",
    "\n",
    "        for a, b in zip(p1, p2):\n",
    "            if start[a] != target[b]:\n",
    "                return False\n",
    "            if not (aa[a] <= b <= bb[a]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "import time\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        pre_r = -1\n",
    "\n",
    "        aa = [0]*n\n",
    "        bb = [0]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            if start[i] == 'R':\n",
    "                pre_r = i\n",
    "            elif start[i] == 'L':\n",
    "                aa[i] = pre_r+1\n",
    "                bb[i] = i\n",
    "\n",
    "        pre_l = n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if start[i] == 'L':\n",
    "                pre_l = i\n",
    "            elif start[i] == 'R':\n",
    "                aa[i] = i\n",
    "                bb[i] = pre_l-1\n",
    "\n",
    "        p1 = [i for i in range(n) if start[i] != '_']\n",
    "        p2 = [i for i in range(n) if target[i] != '_']\n",
    "        if len(p1) != len(p2):\n",
    "            return False\n",
    "        \n",
    "        for a, b in zip(p1, p2):\n",
    "            if start[a] != target[b]:\n",
    "                return False\n",
    "            if not (aa[a] <= b <= bb[a]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        right = [-1] * n #右边第一个左\n",
    "        left = [n] * n #左边第一个右\n",
    "        a,b, arr = [],[],[]\n",
    "        for i, x in enumerate(start):\n",
    "            if(x == 'L' or x == 'R'):\n",
    "                a.append(x)\n",
    "                arr.append((i,x))\n",
    "\n",
    "            if(x == 'R'):\n",
    "                left[i] = i\n",
    "            else:\n",
    "                left[i] = left[i-1] if i-1>=0 else -1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(start[i] == 'L'):\n",
    "                right[i] = i\n",
    "            else:\n",
    "                right[i] = right[i+1] if i+1<n else n\n",
    "\n",
    "        for i, x in enumerate(target):\n",
    "            if(x == 'L' or x == 'R'):\n",
    "                b.append(x)\n",
    "\n",
    "        if ''.join(a) != ''.join(b):\n",
    "            return False\n",
    "        \n",
    "        j = 0\n",
    "        for i, x in enumerate(target):\n",
    "            if(x == '_'): continue\n",
    "            old = arr[j][0]\n",
    "\n",
    "            if x == 'L':\n",
    "                #(left[old], old]\n",
    "                if(i <= left[old] or i > old):\n",
    "                    # print(i, x)\n",
    "                    return False\n",
    "            else:\n",
    "                #[old, right[old])\n",
    "                if(i < old or i >= right[old]):\n",
    "                    # print(i, x)\n",
    "                    return False\n",
    "            j += 1\n",
    "                \n",
    "        return True\n",
    "\n",
    "# print(Solution().canChange(\"_L__R__R_\", \"L______RR\"))\n",
    "# print(Solution().canChange(\"R_L_\", \"__LR\"))\n",
    "# print(Solution().canChange(\"_R\", \"R_\"))\n",
    "# print(Solution().canChange(\"LLRRLRRRRLLLL\", \"LLRRLRRRRLLLL\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if \"\".join(start.split(\"_\")) != \"\".join(target.split(\"_\")):\n",
    "            return False\n",
    "        n = len(start)\n",
    "        target = list(target)\n",
    "        cnt = 0\n",
    "        LLimit = []#左开右闭\n",
    "        preR = -1\n",
    "        for i in range(n):\n",
    "            if start[i] == \"R\":\n",
    "                preR = i\n",
    "            elif start[i] == \"L\":\n",
    "                LLimit.append([preR, i])\n",
    "                preR += 1\n",
    "        preL = n\n",
    "        RLimit = [] # 左闭右开\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if start[i] == \"L\":\n",
    "                preL = i\n",
    "            elif start[i] == \"R\":\n",
    "                RLimit.append([i, preL])\n",
    "                preL -= 1\n",
    "        Lcnt, Rcnt = 0,len(RLimit)-1\n",
    "        for i in range(n):\n",
    "            if target[i] == \"L\":\n",
    "                if Lcnt >= len(LLimit):\n",
    "                    return False\n",
    "                l, r = LLimit[Lcnt]\n",
    "                Lcnt += 1\n",
    "                if l<i<=r:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            elif target[i] == \"R\":\n",
    "                if Rcnt < 0:\n",
    "                    return False\n",
    "                l, r = RLimit[Rcnt]\n",
    "                Rcnt -= 1\n",
    "                if l<=i<r:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "        return Lcnt==len(LLimit) and Rcnt == -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        R_flag = 0\n",
    "        l_start = []\n",
    "        r_start = []\n",
    "        for i in range (0, n):\n",
    "            if start[i] == 'R':\n",
    "                r_start.append(i)\n",
    "                R_flag = 1\n",
    "            elif start[i] == 'L':\n",
    "                apd = [i]\n",
    "                if R_flag == 1:\n",
    "                    apd.append(len(r_start) - 1)\n",
    "                l_start.append(apd)\n",
    "        l_target = []\n",
    "        r_target = []\n",
    "        for i in range (0, n):\n",
    "            if target[i] == 'L':\n",
    "                l_target.append(i)\n",
    "                if len(l_target) > len(l_start):\n",
    "                    return False\n",
    "                if i > l_start[len(l_target) - 1][0]:\n",
    "                    return False\n",
    "            elif target[i] == 'R':\n",
    "                r_target.append(i)\n",
    "                if len(r_target) > len(r_start):\n",
    "                    return False\n",
    "                if i < r_start[len(r_target) - 1]:\n",
    "                    return False\n",
    "        if len(l_start) != len(l_target) or len(r_start) != len(r_target):\n",
    "            return False\n",
    "        for i in range (len(l_start)):\n",
    "            if len(l_start[i]) > 1 and r_target[l_start[i][1]] > l_target[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "import time\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        pre_r = -1\n",
    "\n",
    "        aa = [0]*n\n",
    "        bb = [0]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            if start[i] == 'R':\n",
    "                pre_r = i\n",
    "            elif start[i] == 'L':\n",
    "                aa[i] = pre_r+1\n",
    "                bb[i] = i\n",
    "\n",
    "        pre_l = n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if start[i] == 'L':\n",
    "                pre_l = i\n",
    "            elif start[i] == 'R':\n",
    "                aa[i] = i\n",
    "                bb[i] = pre_l-1\n",
    "\n",
    "        p1 = [i for i in range(n) if start[i] != '_']\n",
    "        p2 = [i for i in range(n) if target[i] != '_']\n",
    "        if len(p1) != len(p2):\n",
    "            return False\n",
    "\n",
    "        for a, b in zip(p1, p2):\n",
    "            if start[a] != target[b]:\n",
    "                return False\n",
    "            if not (aa[a] <= b <= bb[a]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        ini = []\n",
    "        en = []\n",
    "        for i in range(len(start)):\n",
    "            if start[i] in [\"L\",\"R\"]:\n",
    "                ini.append((i,start[i]))\n",
    "            if target[i] in [\"L\",\"R\"]:\n",
    "                en.append((i,target[i]))\n",
    "        if len(ini) != len(en):\n",
    "            return False\n",
    "        for i in range(len(ini)):\n",
    "            if ini[i][1] != en[i][1]:\n",
    "                return False\n",
    "            if ini[i][1] == \"L\" and en[i][0] > ini[i][0]:\n",
    "                return False\n",
    "            if ini[i][1] == \"R\" and en[i][0] < ini[i][0]:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        dtl,dtr={},{}\n",
    "        n=len(start)\n",
    "        pr=-1\n",
    "        for i in range(n):\n",
    "            if start[i]==\"L\":\n",
    "                dtl[i]=pr\n",
    "            if start[i]==\"R\":\n",
    "                pr=i\n",
    "        dt=Counter(target)\n",
    "        if dt[\"L\"]!=len(dtl):\n",
    "            return False\n",
    "        tl,tr=[],[]\n",
    "        for i in range(n):\n",
    "            if target[i]==\"L\":\n",
    "                tl.append(i)\n",
    "            if target[i]==\"R\":\n",
    "                tr.append(i)\n",
    "        sl=list(dtl)\n",
    "        for i in range(len(sl)):\n",
    "            if sl[i]<tl[i]:\n",
    "                return False\n",
    "            if tl[i]<=dtl[sl[i]]:\n",
    "                return False\n",
    "        temp=\"\"\n",
    "        for i in range(n):\n",
    "            if target[i]==\"L\":\n",
    "                temp+=\"L\"\n",
    "            else:\n",
    "                temp+=start[i]\n",
    "        start=temp\n",
    "        bl = n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if start[i] == \"R\":\n",
    "                dtr[i] = bl\n",
    "            if start[i] == \"L\":\n",
    "                bl = i\n",
    "        if dt[\"R\"]!=len(dtr):\n",
    "            return False\n",
    "        sr=list(dtr)[::-1]\n",
    "        for i in range(len(sr)):\n",
    "            if sr[i]>tr[i]:\n",
    "                return False\n",
    "            if tr[i]>=dtr[sr[i]]:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def haha(str1):\n",
    "    str_new = str1.replace(\"_\", \"\")\n",
    "    return str_new\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        start_temp = haha(start)\n",
    "        target_temp = haha(target)\n",
    "        if start_temp != target_temp:\n",
    "            return False\n",
    "        len1 = len(start_temp)\n",
    "        dp = [[0 for i in range(2)] for j in range(len1)]\n",
    "        len_start = len(start)\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(len_start):\n",
    "            if start[i] != \"_\":\n",
    "                dp[cnt][0] = i\n",
    "                cnt += 1\n",
    "\n",
    "        len_target = len(target)\n",
    "        cnt = 0\n",
    "        for i in range(len_target):\n",
    "            if target[i] != \"_\":\n",
    "                dp[cnt][1] = i\n",
    "                cnt += 1\n",
    "        for i in dp:\n",
    "            print(i, start[i[0]])\n",
    "            if start[i[0]] == \"L\":\n",
    "                if i[0] < i[1]:\n",
    "                    return False\n",
    "            else:\n",
    "                if i[0] > i[1]:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n=len(start)\n",
    "        wait_1,wait_2=[],[]\n",
    "        for i in range(n):\n",
    "            if start[i]!='_':\n",
    "                wait_1.append((start[i],i))\n",
    "            if target[i]!='_':\n",
    "                wait_2.append((target[i],i))\n",
    "        if len(wait_1)!=len(wait_2):\n",
    "            return False\n",
    "        while wait_1:\n",
    "            t1,t2=wait_1.pop(),wait_2.pop()\n",
    "            if t1[0]!=t2[0]:\n",
    "                return False\n",
    "            if t1[0]=='R' :\n",
    "                if t1[1]>t2[1]:\n",
    "                    return False\n",
    "            elif t1[1]<t2[1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s = []\n",
    "        t = []\n",
    "        n = len(start)\n",
    "        for i in range(n):\n",
    "            if start[i] != '_':\n",
    "                s.append((i, start[i]))\n",
    "            if target[i] != '_':\n",
    "                t.append((i, target[i]))\n",
    "        m, n = len(s), len(t)\n",
    "        if m != n:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if s[i][1] != t[i][1]:\n",
    "                return False\n",
    "            if s[i][1] == 'L' and s[i][0] < t[i][0]:\n",
    "                return False\n",
    "            if s[i][1] == 'R' and s[i][0] > t[i][0]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n = len(start)\n",
    "        empty = 0\n",
    "        char_s = []\n",
    "        for c in start:\n",
    "            if c == '_':\n",
    "                empty += 1\n",
    "            else:\n",
    "                char_s.append([empty,c])\n",
    "                empty = 0\n",
    "\n",
    "        empty = 0\n",
    "        char_t = []\n",
    "        for c in target:\n",
    "            if c == '_':\n",
    "                empty += 1\n",
    "            else:\n",
    "                char_t.append([empty,c])\n",
    "                empty = 0\n",
    "\n",
    "        if len(char_s) != len(char_t):\n",
    "            return False \n",
    "        \n",
    "        offset = 0\n",
    "        for i in range(len(char_s)):\n",
    "            c = char_s[i][-1]\n",
    "            if c != char_t[i][-1]:\n",
    "                return False \n",
    "            if c == 'L' and char_s[i][0] + offset < char_t[i][0]:\n",
    "                return False \n",
    "            if c == 'R' and char_s[i][0] + offset > char_t[i][0]:\n",
    "                return False \n",
    "            \n",
    "            offset = char_s[i][0] + offset - char_t[i][0]\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        d1 = collections.Counter(start)\n",
    "        d2 = collections.Counter(target)\n",
    "        if d1 != d2:\n",
    "            return False\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "        for i in range(len(start)):\n",
    "            if start[i] != '_':\n",
    "                s1.append(start[i])\n",
    "            if target[i] != '_':\n",
    "                s2.append(target[i])\n",
    "        if s1 != s2:\n",
    "            print(\"位置不匹配\")\n",
    "            return False\n",
    "        d1 = []\n",
    "        d2 = []\n",
    "        for i in range(len(start)):\n",
    "            if start[i] != '_':\n",
    "                d1.append((start[i], i))\n",
    "            if target[i] != '_':\n",
    "                d2.append((target[i], i))\n",
    "        for i in range(len(d1)):\n",
    "            if d1[i][0] == 'L':\n",
    "                if d1[i][1] < d2[i][1]:\n",
    "                    return False\n",
    "            else:\n",
    "                if d1[i][1] > d2[i][1]:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if start.replace(\"_\",\"\") != target.replace(\"_\",\"\"): return False\n",
    "        n = len(start)\n",
    "        sl,sr=[0]*n,[0]*n\n",
    "        tl,tr=[0]*n,[0]*n\n",
    "        for i in range(n):\n",
    "            if start[i]=='L':sl[i]=1\n",
    "            if start[i]=='R':sr[i]=1\n",
    "            if target[i]=='L':tl[i]=1\n",
    "            if target[i]=='R':tr[i]=1\n",
    "        ssl = list(accumulate(sl))\n",
    "        stl = list(accumulate(tl))\n",
    "        ssr = list(accumulate(sr))\n",
    "        str = list(accumulate(tr))\n",
    "        return not(any(x<y for x,y in zip(ssr,str)) or any(x>y for x,y in zip(ssl,stl)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "import math\n",
    "from typing import List\n",
    "from collections import Counter, deque, defaultdict\n",
    "from bisect import *\n",
    "from heapq import heappop, heappush, heapify\n",
    "from functools import lru_cache\n",
    "from itertools import accumulate, product\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        lcnt, rcnt = Counter(start), Counter(target)\n",
    "        if lcnt['_'] != rcnt['_'] or lcnt['L'] != rcnt['L'] or lcnt['R'] != rcnt['R']:\n",
    "            return False\n",
    "        def findPos(arr):\n",
    "            lcount = rcount = 0\n",
    "            cnt = defaultdict(int)\n",
    "            for c in arr:\n",
    "                if c == 'L':\n",
    "                    lcount += 1\n",
    "                    cnt[lcount] = rcount\n",
    "                if c == 'R':\n",
    "                    rcount += 1\n",
    "            lcount += 1\n",
    "            cnt[lcount] = rcount\n",
    "            return cnt\n",
    "\n",
    "        s = findPos(start) # 先判断相对位置是否有问题\n",
    "        t = findPos(target)\n",
    "\n",
    "        for i in range(1, len(s) + 1):\n",
    "            if s[i] != t[i]:\n",
    "                return False\n",
    "\n",
    "        def getPos(arr, c):\n",
    "            p = []\n",
    "            for i, x in enumerate(arr):\n",
    "                if x == c:\n",
    "                    p.append(i)\n",
    "\n",
    "            return p\n",
    "\n",
    "        ls = getPos(start, 'L')\n",
    "        lt = getPos(target, 'L')\n",
    "        # print(ls, lt)\n",
    "        for i in range(len(ls)):\n",
    "            if ls[i] < lt[i]:\n",
    "                return False\n",
    "\n",
    "        rs = getPos(start, 'R')\n",
    "        rt = getPos(target, 'R')\n",
    "        for i in range(len(rs)):\n",
    "            if rs[i] > rt[i]:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if start.replace(\"_\",\"\") != target.replace(\"_\",\"\"): return False\n",
    "        n = len(start)\n",
    "        sl,sr=[0]*n,[0]*n\n",
    "        tl,tr=[0]*n,[0]*n\n",
    "        for i in range(n):\n",
    "            if start[i]=='L':sl[i]=1\n",
    "            if start[i]=='R':sr[i]=1\n",
    "            if target[i]=='L':tl[i]=1\n",
    "            if target[i]=='R':tr[i]=1\n",
    "        ssl = list(accumulate(sl))\n",
    "        stl = list(accumulate(tl))\n",
    "        if any(x>y for x,y in zip(ssl,stl)):return False\n",
    "        ssr = list(accumulate(sr))\n",
    "        str = list(accumulate(tr))\n",
    "        \n",
    "        if any(x<y for x,y in zip(ssr,str)): return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        st=[]\n",
    "        tr=[]\n",
    "        for i in range(len(start)):\n",
    "            if start[i]=='L':\n",
    "                st.append(['L',i])\n",
    "            elif start[i]=='R':\n",
    "                st.append(['R',i])\n",
    "            if target[i]=='L':\n",
    "                tr.append(['L',i])\n",
    "            elif target[i]=='R':\n",
    "                tr.append(['R',i])\n",
    "        if len(st)!=len(tr):\n",
    "            return False\n",
    "        n=len(st)\n",
    "        for i in range(n):\n",
    "            if st[i][0]!=tr[i][0]:\n",
    "                return False\n",
    "            if st[i][0]=='L':\n",
    "                if st[i][1]<tr[i][1]:\n",
    "                    return False\n",
    "            else:\n",
    "                if st[i][1]>tr[i][1]:\n",
    "                    return False\n",
    "        return True\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if len(start) != len(target) or start.replace('_', '') != target.replace('_', ''):\n",
    "            return False\n",
    "        import numpy as np\n",
    "        l1 = np.array(list(start))\n",
    "        l2 = np.array(list(target))\n",
    "        x1 = np.where(l1 == 'L')[0]\n",
    "        x2 = np.where(l2 == 'L')[0]\n",
    "        if not (x1 >= x2).all():\n",
    "            return False\n",
    "        return True if (np.where(l1 == 'R')[0] <= np.where(l2 == 'R')[0]).all() else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        m, n = len(start), len(target)\n",
    "\n",
    "        if start.replace('_', '') != target.replace('_', ''):\n",
    "            return False\n",
    "\n",
    "        # prefix_start[i]: start[i] 左侧空格数\n",
    "        prefix_start = [0] * m\n",
    "        for i in range(1, m):\n",
    "            prefix_start[i] = prefix_start[i - 1] + (start[i - 1] == '_')\n",
    "\n",
    "        # suffix_start[i]: start[i] 右侧空格数\n",
    "        suffix_start = [0] * m\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            suffix_start[i] = suffix_start[i + 1] + (start[i + 1] == '_')\n",
    "\n",
    "        # prefix_target[i]: target[i] 左侧空格数\n",
    "        prefix_target = [0] * m\n",
    "        for i in range(1, m):\n",
    "            prefix_target[i] = prefix_target[i - 1] + (target[i - 1] == '_')\n",
    "        \n",
    "        # suffix_target[i]: target[i] 右侧空格数\n",
    "        suffix_target = [0] * m\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            suffix_target[i] = suffix_target[i + 1] + (target[i + 1] == '_')\n",
    "\n",
    "        startl2idx = []\n",
    "        startr2idx = []\n",
    "        for i in range(m):\n",
    "            if start[i] == 'L':\n",
    "                startl2idx.append(i)\n",
    "            elif start[i] == 'R':\n",
    "                startr2idx.append(i)\n",
    "\n",
    "        targetl2idx = []\n",
    "        targetr2idx = []\n",
    "        for i in range(n):\n",
    "            if target[i] == 'L':\n",
    "                targetl2idx.append(i)\n",
    "            elif target[i] == 'R':\n",
    "                targetr2idx.append(i)\n",
    "\n",
    "        for sl, tl in zip(startl2idx, targetl2idx):\n",
    "            # 如果 start L 左侧空格数小于 tartget L 左侧空格数，\n",
    "            # 那么，不能由 start 变成 target\n",
    "            if prefix_start[sl] < prefix_target[tl]:\n",
    "                return False\n",
    "            \n",
    "        for sr, tr in zip(startr2idx[::-1], targetr2idx[::-1]):\n",
    "            # 如果 start R 右侧空格数小于 target R 右侧空格数\n",
    "            # 那么，不能由 start 变成 target\n",
    "            if suffix_start[sr] < suffix_target[tr]:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        if list(start).count('L') != list(target).count('L') or list(start).count('R') != list(target).count('R') or start.replace(\"_\", \"\") != target.replace(\"_\", \"\"):\n",
    "            return False\n",
    "        rs, ls = [], []\n",
    "        cnt_r, cnt_l = 0, 0\n",
    "        for i, j in enumerate(target):\n",
    "            if j == \"R\":\n",
    "                rs.append([i])\n",
    "                cnt_r += 1\n",
    "            if j == \"L\":\n",
    "                ls.append([i])\n",
    "                cnt_l += 1\n",
    "        for i, j in enumerate(start):\n",
    "            if j == \"R\":\n",
    "                rs[len(rs) - cnt_r].append(i)\n",
    "                cnt_r -= 1\n",
    "            if j == \"L\":\n",
    "                ls[len(ls) - cnt_l].append(i)\n",
    "                cnt_l -= 1\n",
    "        for i in rs:\n",
    "            if i[0] < i[1]:\n",
    "                return False\n",
    "        for i in ls:\n",
    "            if i[0] > i[1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        n=len(start)\n",
    "        tmp1=[]\n",
    "        tmp2=[]\n",
    "        for i in range(n):\n",
    "            if start[i]!=\"_\":\n",
    "                tmp1.append([start[i],i])\n",
    "            if target[i]!=\"_\":\n",
    "                tmp2.append([target[i],i])\n",
    "        if len(tmp1)!=len(tmp2):\n",
    "            return False\n",
    "        for s1,s2 in zip(tmp1,tmp2):\n",
    "            c1,x1=s1\n",
    "            c2,x2=s2\n",
    "            if c1!=c2:\n",
    "                return False\n",
    "            if c1==\"L\":\n",
    "                if x2>x1:\n",
    "                    return False \n",
    "            else:\n",
    "                if x2<x1:\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canChange(self, start: str, target: str) -> bool:\n",
    "        s1 = []\n",
    "        for i, x in enumerate(start):\n",
    "            if x != '_':\n",
    "                s1.append((i, x))\n",
    "        \n",
    "        s2 = []\n",
    "        for i, x in enumerate(target):\n",
    "            if x != '_':\n",
    "                s2.append((i, x))\n",
    "        if len(s1) != len(s2):\n",
    "            return False\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i][1] != s2[i][1]:\n",
    "                return False\n",
    "            if s1[i][1] == 'L':\n",
    "                if s1[i][0] < s2[i][0]:\n",
    "                    return False\n",
    "            if s1[i][1] == 'R':\n",
    "                if s1[i][0] > s2[i][0]:\n",
    "                    return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
